package leetcode_union_and_find;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 128.最长连续序列
 * 算法：哈希表、哈希表 + 并查集
 *
 * @author yezh
 * @date 2023/12/25 11:23
 */
public class _128 {

    public int longestConsecutive_hash(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int ans = 0;
        for (int num : nums)
            if (!set.contains(num - 1)) {
                int cnt = 1;
                while (set.contains(++num)) ++cnt;
                ans = Math.max(ans, cnt);
            }
        return ans;
    }

    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        UF uf = new UF(nums.length);
        for (int i = 0; i < nums.length; i++)
            if (!map.containsKey(nums[i])) {
                if (map.containsKey(nums[i] - 1)) uf.union(i, map.get(nums[i] - 1));
                if (map.containsKey(nums[i] + 1)) uf.union(i, map.get(nums[i] + 1));
                map.put(nums[i], i);
            }
        return uf.getMaxConnection();
    }

    class UF {
        int[] p;

        public UF(int n) {
            p = new int[n];
            for (int i = 0; i < n; i++) p[i] = -1;
        }

        public void union(int x, int y) {
            int px = find(x), py = find(y);
            // 小的树往大的树合, 平衡树, 使树的深度尽量小
            if (-p[px] > -p[py]) {
                p[px] += p[py];
                p[py] = px;
            } else {
                p[py] += p[px];
                p[px] = py;
            }
        }

        public int find(int x) {
            int px = x;
            if (p[px] >= 0) {
                px = find(p[px]);
                // 路径压缩
                p[x] = px;
            }
            return px;
        }

        public int getMaxConnection() {
            int ans = 0;
            for (int cnt : p) if (cnt < 0) ans = Math.max(ans, -cnt);
            return ans;
        }

    }

}
